#include "pch.h"
#include "BinaryTree.h"

template<class I, class T>
BinaryTree<I, T>::BinaryTree(IComparer* comparer)
{
	this->Comparer = comparer;

	this->Index = NULL;
	this->Item = NULL;

	this->Left = NULL;
	this->Right = NULL;
}

template<class I, class T>
T BinaryTree<I, T>::FindItem(I index)
{
	if (this->Index == index)
	{
		return this->Item;
	}
	else
	{
		// if the comparer returns less than 0 then follow the left branch of the tree
		// to find the item.
		if (this->Comparer->Compare(&index, &this->Index) < 0)
		{
			if (this->Left != NULL)
			{
				return this->Left->FindItem(index);
			}
		}
		else
		{
			// the comparer returned a value 0 or greater, so follow
			// the right branch to find the item.
			if (this->Right != NULL)
			{
				return this->Right->FindItem(index);
			}
		}

		// Index doesn't appear to exist, so return null
		return NULL;
	}
}

template<class I, class T>
void BinaryTree<I, T>::AddItem(I index, T item)
{
	if (this->Index == NULL)
	{
		this->Index = index;
		this->Item = item;
	}
	else
	{
		// if the comparer returns less than 0 then follow the left branch of the tree
		// to add the item.
		if (this->Comparer->Compare(&index, &this->Index) < 0)
		{
			if (this->Left != NULL)
			{
				this->Left->AddItem(index, item);
			}
			else
			{
				this->Left = new BinaryTree<I, T>(this->Comparer);

				this->Left->AddItem(index, item);
			}
		}
		else
		{
			if (this->Right != NULL)
			{
				this->Right->AddItem(index, item);
			}
			else
			{
				this->Right = new BinaryTree<I, T>(this->Comparer);

				this->Right->AddItem(index, item);
			}
		}
	}
}

